class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int k) {
        int f[110][110];
        int res[110] = { 0 };
        memset(f, 0x3f, sizeof(f));
        for (auto x : edges) {
            int a = x[0];
            int b = x[1];
            f[a][a] = 0;
            f[b][b] = 0;
            f[a][b] = f[b][a] = min(f[a][b], x[2]);
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
                }
            }
        }
        //int ans = 0;
        //for (int i = 0; i < n; i++) {
        //    for (int j = 0; j < n; j++) {
        //        if (i == j)continue;
        //        if (f[i][j] <= k) {
        //            // cout<<"i=="<<i<<endl;
        //            // cout<<"j=="<<j<<endl;
        //            // cout<<"f[i][j]=="<<f[i][j]<<endl;
        //            res[i]++;
        //        }
        //    }
        //    cout << "i==" << i << endl;
        //    cout << "cnt==" << res[i] << endl;
        //}
        //int cnt = 1e9;
        //for (int i = 0; i < n; i++) {
        //    if (cnt >= res[i]) {
        //        cnt = res[i];
        //        cout << "i==" << i << endl;
        //        cout << "cnt==" << cnt << endl;
        //        ans = max(ans, i);
        //    }
        //}
        //return ans;
        int ans = 0, cnt = 1e9;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = 0; j < n; j++) {
                if (i == j)continue;
                if (f[i][j] <= k) {
                    sum++;
                }
            }
            if (cnt >= sum) {
                cnt = sum;
                ans = max(ans, i);
            }
        }
        return ans;
    }
};